/**
 * https://www.bilibili.com/video/BV1AY4y157yL
 *
 * a[0~k]=a[m~m+k] 叫做一个串对,它对应一个双射 f: 0<->m,k<->m+k
 * buildNext('abcabcaa')=[-1,-1,-1,0,1,2,3,0]
 * next[k]: 定义如下
 * P1: f(k);  a[0:k]可形成的最大串对
 * P2: -1;    a[0:k]无法形成串对
 * next[k] 的值由a[0~k]唯一确定
 * 构造next数组
 * @param patt
 * @returns {number[]}
 */
function buildNext(patt){
    //前面一个字符匹配的位置
    let k = -1;
    let next = [-1];
    for(let j=1;j<patt.length;j++){
        //不匹配则向前回溯
        if(patt[j]!==patt[k+1]){
              while(k>-1){k=next[k];}
        }else{
             k = k+1;
        }
        next[j] = k;
    }
    return next;
}

/**
 * kmp
 * @param str {string}主串
 * @param patt {string}模式串
 * @returns {number}
 */
function kmp(str,patt){
    let next = buildNext(patt);
    let i = 0;//当前匹配的str的字符的下标
    let j = 0;//当前匹配的单词的字符的下标
    while(i<str.length&&j<patt.length){
        if(j==-1||str[i]==patt[j]){//如果匹配，则匹配下一个字符
            i=i+1;
            j=j+1;
        }else{//如果不匹配，对patt从next[j]开始匹配
            j = next[j];
        }
    }
    if(j==patt.length){//匹配成功
        return i-patt.length;
    }
    return -1;
}



function test(){
  //  let str = 'hello1 opo123 lavign e opopopo';
   // let patt = 'opo123';
  //  let r = kmp(str,patt);
   // console.info(r);
    console.log( buildNext("abcabcaa"))

}




test();